package basic.study.leetcode;

import java.util.*;

/**
 * @ClassName Mid210
 * @Description 拓扑排序   先修课程
 * @Company inspur
 * @Author Kevin
 * @Date 2020/5/17 21:06
 * @Version 1.0
 */
public class Mid210 {
    /**
     * 第一个题解
     */
    class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites){
            //入度表
            int[] inDegree = new int[numCourses];
            //依赖关系
            HashMap<Integer, List<Integer>> map = new HashMap<>();
            //当前入度为0的
            Queue<Integer> queue = new LinkedList<>();
            //创建入度表和哈希表
            for (int i = 0; i < prerequisites.length; i++) {
                //入度
                inDegree[prerequisites[i][0]]++;
                if(map.containsKey(prerequisites[i][1])){
                    //先决 :-> 后续
                    map.get(prerequisites[i][1]).add(prerequisites[i][0]);
                } else {
                    List<Integer> list = new ArrayList<>();
                    list.add(prerequisites[i][0]);
                    map.put(prerequisites[i][1], list);
                }
            }
            //遍历，将index入队
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < numCourses; i++) {
                if(inDegree[i] == 0){
                    queue.offer(i);
                }
            }
            // 出队，查哈希表，将入度为零的入队
            while (!queue.isEmpty()){
                Integer cur = queue.poll();
                res.add(cur);
                if(map.containsKey(cur) && map.get(cur).size() != 0){
                    for (Integer num : map.get(cur)) {
                        inDegree[num]--;
                        if(inDegree[num] == 0) queue.offer(num);
                    }
                }
            }
            //使用list的流来转为int[]数组，也可以通过遍历一遍完成转换。
            return res.size() == numCourses ? res.stream().mapToInt(Integer::valueOf).toArray() : new int[0];
        }
    }





    /**
     * 第二个题解
     */
    boolean hasCycle;
    Deque<Integer> reversePost = new LinkedList<>();

    public int[] findOrder(int V, int[][] A) {
        // 将边缘列表变为邻接列表
        List<Integer>[] G = (List<Integer>[])new ArrayList[V];
        for (int i = 0; i < V; i++) G[i] = new ArrayList<>();
        //先决条件： 后续
        for (int[] a : A) G[a[1]].add(a[0]);

        int[] ans = new int[]{};

        findCycle(V, G);
        // 只有无环才能拓扑排序
        if (!hasCycle) {
            ans = new int[reversePost.size()];
            for (int i = 0; i < ans.length; i++) {
                ans[i] = reversePost.pop();
            }
        }
        return ans;
    }

    void findCycle(int V, List<Integer>[] G) {
        boolean[] seen = new boolean[V];
        boolean[] onstack = new boolean[V];
        for (int v = 0; v < V; v++) {
            if (!seen[v]) dfs(v, G, seen, onstack);
        }
    }

    void dfs(int v, List<Integer>[] G, boolean[] seen, boolean[] onstack) {
        if (hasCycle) return;
        seen[v] = true;
        onstack[v] = true;
        for (int w : G[v]) {
            if (!seen[w]) dfs(w, G, seen, onstack);
            //seen[w] = true and onstack[w] = true
            else if (onstack[w]) {
                hasCycle = true;
                return;
            }
        }
        // 找环的同时进行记录拓扑排序
        reversePost.push(v);
        onstack[v] = false;
    }

//    作者：dan-huang-jiang-xing-ren
//    链接：https://leetcode-cn.com/problems/course-schedule-ii/solution/javaji-yu-suan-fa-4-de-shi-xian-by-dan-huang-jiang/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}
